# 45.跳跃游戏II
# 给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳
# 转到任意nums[i + j]处:
# 0 <= j <= nums[i]
# i + j < n
# 返回到达nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[n - 1]。
#
# 示例1:
# 输入: nums = [2, 3, 1, 1, 4]
# 输出: 2
# 解释: 跳到最后一个位置的最小跳跃数是2。从下标为0跳到下标为1的位置，跳1步，然后跳3步到达数组的最后一个位置。
#
# 示例2:
# 输入: nums = [2, 3, 0, 1, 4]
# 输出: 2


class Solution:
    def jump(self, nums: [int]) -> int:
        # 解法一也就勉勉强强看懂,解法二先不抄了,真不懂
        if len(nums) == 1:
            return 0
        cur = 0 # 当前覆盖最远距离下标
        ans = 0 # 记录走的最大步数
        nextd = 0 # 下一步覆盖最远距离下标
        size = len(nums)
        for i in range(size):
            nextd= max(nums[i]+i,nextd) # 更新下一步覆盖最远距离下标
            if i == cur: # 遇到当前覆盖最远距离下标
                if cur != len(nums)-1:  # 如果当前覆盖最远距离下标不是终点
                    ans += 1 # 需要走下一步
                    cur = nextd # 更新当前覆盖最远距离下标（相当于加油了）
                    if nextd >= len(nums) - 1: # 下一步的覆盖范围已经可以达到终点，结束循环
                        break
        return ans


if __name__ == '__main__':
    nums = [2, 3, 1, 1, 4]
    # nums = [1,2,1,1,1]
    tmp = Solution()
    res = tmp.jump(nums)
    print(res)